package shellsort

// 改进的插入排序
// 先找一个间隔，在间隔上的数用插入排序排号，然后间隔缩短，一直到1
// 为什么比插入排序效率高？---- 因为有了间隔，使大序列变成了小序列。
// 跳着排，不稳定。

// 100000 个数 耗时 4.74s
// func ShellSort(array []int) []int {
// 	for grap:=4;grap>0;grap--{
// 		array = InsertSort(array, grap)
// 	}
// 	return array
// }

// 耗时 3.8s 左右
// func ShellSort(array []int) []int {
// 	for grap:=len(array)>>1;grap>0;grap/=2{
// 		array = InsertSort(array, grap)
// 	}
// 	return array
// }

// 经常使用的间隔序列  耗时 3.56s 左右
func ShellSort(array []int) []int {
	var h int = 1
	for h <= len(array)/3 {
		h = 3*h + 1
	}
	for grap := h; grap > 0; grap=(grap-1)/3 {
		array = InsertSort(array, grap)
	}
	return array
}

func InsertSort(array []int, grap int) []int {
	for i := 1; i <= len(array)-grap; i += grap {
		for j := i; j >= 0+grap; j -= grap {
			if array[j] < array[j-grap] {
				array[j], array[j-grap] = array[j-grap], array[j]
			}
		}
	}
	return array
}
